The arithmetic of TCP based on Network Coding (NC-TCP in short) is to mask losses from TCP using random linear coding, thus improve the throughput. This method assures that there is large possibility that the data packets carry new information. Unless the receiver has already the same information as the sender, it will get new information.
We make some important modifications in order to incorporate coding. First, instead of the original packets, we transmit random linear combinations of packets in the congestion window. With a large field size, every random linear combination is very likely to cause the next unseen packet to be seen. So even if a transmitted linear combination is lost, the next successful reception will cause the next unseen packet to be seen. In another words, the loss of the link is presented to TCP as an additional queuing delay that leads to a larger effective round-trip time (RTT). The initial time-up retransmission system is replaced by the redundancy factor R, while R indicates the send times of linear combinations that wait to be sent. The RTT mentioned above has a new explanation, that is, the time that the network transmits a degree. The more losses happened, the larger the RTT is. We choose TCP-Vegas to combine with the network coding theory, the sender marks every time when every linear combination sends. When ACK arrives, it figures out RTT. Second, on the receiver, we bring in a notion called “seeing a packet”. The definition is a node is said to have seen a packet pk if it has enough information to compute a linear combination of the form (pk+q), where q=Σl>kαlpl, with αlεFq for all l>k. Thus, q is a linear combination involving packets with indices larger than k. On the receiver, when it sees a packet pk, it can immediately send back ACK to the sender, rather than waiting to decode this packet. The notion of “seeing a packet” solves the problem of the ACK that may not be sent back to the sender because of the delay of decoding. It seals the network coding theory to TCP.
NC-TCP brings another two notions, the “knowledge of a node” and “virtual queue”. The knowledge of a node is the set of all linear combinations of original packets that it can compute, based on the information it has received so far. The coefficient vectors of these linear combinations from a vector space called the knowledge space of the node. The number of the virtual queues equals the number of the receivers. The length of the jth queue equals to the difference of the dimensions of the knowledge space between the sender and the jth receiver.
All the theories above needs to combine with TCP in a non-imposing way, so MIT invented a NC layer which is between transmission layer and IP layer. The operation describes as follows:
The sender module accepts packets from the TCP source and buffers them into an encoding buffer which represents the coding window, until they are ACKed by the receiver. The sender then generates and sends random linear combinations of the packets in the coding window. The coefficients used in the linear combination are also conveyed in the header.
For every packet that arrives from TCP, R linear combinations are sent to the IP layer on average, where R is the redundancy parameter. The average rate at which linear combinations are sent into the network is thus a constant factor more than the rate at which TCP's congestion window progresses. This is necessary in order to compensate for the loss rate of the channel and to match TCP's sending rate to the rate at which data is actually sent to the receiver. If there is too little redundancy, then the data rate reaching the receiver will not match the sending rate because of the losses. This leads to a situation where the losses are not effectively masked from the TCP layer. Hence, there are frequent timeouts leading to a low throughput. On the other extreme, too much redundancy is also bad, since then the transmission rate becomes limited by the rate of the code itself. Besides, sending too many linear combinations can congest the network. The ideal level of redundancy is to keep R equal to the reciprocal of the probability of successful reception.
Upon receiving a linear combination, the receiver module first retrieves the coding coefficient from the header and appends it to the basis matrix of its knowledge space. Then, it performs a Gaussian elimination to find out which packet is newly seen so that this packet can be ACKed. The receiver module also maintains a buffer of linear combinations of packets that have not been decoded yet. In addition, when the receiver sees a packet, it informs the sender and the sender will discard this packet.
In NC-TCP, the redundancy factor R is fixed, we need to know the loss rate of the network circumstance, and set R to the optimal number. However, when the system is under lossy networks, especially wireless network where the loss rate is not constant, the constant redundancy factor R may cause problems, either sending bunches of useless redundancy packets or being not able to mask the packets loss. Both will impair the performance of the network.